package 简单算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-17
 * @Description: 给定一个旋转排序数组，在原地恢复其排序。
 * 样例
 * Example1:
 * [4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
 * Example2:
 * [6,8,9,1,2] -> [1,2,6,8,9]
 * 挑战
 * 使用O(1)的额外空间和O(n)时间复杂度
 **/
public class 恢复旋转排序数组 {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(4);
        nums.add(5);
        nums.add(6);
        nums.add(1);
        nums.add(2);
        nums.add(3);
        恢复旋转排序数组 s = new 恢复旋转排序数组();
        s.recoverRotatedSortedArray(nums);
        System.out.println(nums);
    }

    private void reverse(List<Integer> nums, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = nums.get(i);
            nums.set(i, nums.get(j));
            nums.set(j, temp);
        }
    }

    public void recoverRotatedSortedArray(List<Integer> nums) {
//        for (int index = 0; index < nums.size() - 1; index++) {
//            if (nums.get(index) > nums.get(index + 1)) {
//                reverse(nums, 0, index);
//                reverse(nums, index + 1, nums.size() - 1);
//                reverse(nums, 0, nums.size() - 1);
//            }
//        }

        //[4, 5, 3, 2, 1] -> [1, 2, 3, 4, 5]
        // 5 3 2 1 4
        //3 2 1 4 5
        int count = 0;
        while (nums.get(0) < nums.get(1) && count < nums.size() - 1) {
            nums.add(nums.get(0));
            nums.remove(0);
            count++;
        }
        nums.add(nums.get(0));
        nums.remove(0);
    }
}
